package basic.sort.heap;

import basic.sort.utils.SwapUtil;
import com.sun.org.apache.xerces.internal.dom.PSVIAttrNSImpl;

import java.util.ArrayList;
import java.util.Optional;
import java.util.PriorityQueue;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.heap
 * @since JDK1.8
 */
public class Heap {

    private static class MyHeap {
        private int[] heap; // 底层存储结构
        private int heapSize; // 堆中元素大小
        private int limit; // 最大元素

        public MyHeap(int limit) {
            this.heap = new int[limit];
            this.heapSize = 0;
            this.limit = limit;
        }

        // 插入
        public void push(int value) {
            // 判断堆是否满了
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }

            // 赋值
            heap[heapSize] = value;
            // 插入值
            heapInsert(heapSize++);
        }

        public int pop() {
            // 判断是否为空
            if (isEmpty()) {
                throw new RuntimeException("heap is empty");
            }

            // 将要弹出的最大值
            int ans = heap[0];
            // 交换最末元素和顶部
            swap(0, --heapSize);
            // 重新保持堆的结构稳定
            heapIfy(0, heapSize);
            // 返回最大值
            return ans;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public boolean isFull() {
            return heapSize == limit;
        }

        // 一个一个节点向堆中插入
        // 新加进来的数，现在停在了index位置，请依次往上移动，
        // 移动到0位置，或者干不掉自己的父亲了，停！
        private void heapInsert(int index) {
            while (heap[index] > heap[(index - 1) / 2]) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        // 批量数据构建一个堆
        private void heapIfy(int index, int heapSize) {
            // 左孩子坐标
            int left = index * 2 + 1;
            // 循环构建
            while (left < heapSize) {
                // 获取左右孩子中较大坐标
                int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
                // 比较孩子结点大小和父节点大小
                largest = heap[largest] > heap[index] ? largest : index;
                // 判断父节点是否是最大
                if (largest == index) {
                    break;
                }

                // index和较大孩子，要互换
                swap(largest, index);
                // 更新值
                index = largest;
                left = index * 2 + 1;
            }
        }

        // 交换函数
        private void swap(int a, int b) {
            int temp = heap[a];
            heap[a] = heap[b];
            heap[b] = temp;
        }
    }

    public static class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }

        public int pop() {
            int maxIndex = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            arr[maxIndex] = arr[--size];
            return ans;
        }

    }

    public static void main(String[] args) {
        int value = 1000;
        int limit = 10;
        int testTimes = 10;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MyHeap my = new MyHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        System.out.println("Oops! full pop");
                    }
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops! pop");
                        }
                    }
                }
            }
        }
        System.out.println("finish!");
    }

}
